package 数据结构专栏.简单级别;

/**
 * @DESC TODO
 * @Author tzq
 * @Date 2020-03-27 11:47
 **/
public class _28_实现strStr {
    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";
        System.out.println(strStr(haystack, needle));


    }


    /**
     * 方法一：子串逐一比较 - 线性时间复杂度
     *
     * 复杂度分析
     *
     * 时间复杂度：O((N - L)L)O((N−L)L)，其中 N 为 haystack 字符串的长度，L 为 needle 字符串的长度。内循环中比较字符串的复杂度为 L，总共需要比较 (N - L) 次。
     *
     * 空间复杂度：O(1)
     *
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {

        int l = needle.length(), n = haystack.length();

        for (int i = 0; i < n - l + 1; i++) {
            if (haystack.substring(i, i + l).equals(needle)) {
                return i;
            }
        }
        return -1;

    }


    /**
     * 最普通解法，面试官肯定不希望这样写
     * 输入: haystack = "hello", needle = "ll"
     * 输出: 2
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr2(String haystack, String needle) {
        if (haystack.length() == 0 || needle.length() == 0) return -1;
        return haystack.indexOf(needle);
    }
}
